package 笔试题;

/**
 * https://leetcode.cn/problems/escape-the-spreading-fire/?envType=daily-question&envId=2023-11-09
 */

public class lk_2258逃离火灾 {
    public static void main(String[] args) {
        lk_2258逃离火灾 m = new lk_2258逃离火灾();

//        int[][] grid = {{0,0,0,1,0,1,0,2,1,1,0,0,2,0,2,0,1,1,1,1,0,0,0,2,0,1,2,2,2,1},{2,2,0,1,2,1,1,1,0,2,2,1,2,1,2,1,1,0,0,1,0,1,0,0,1,2,1,1,0,1},{1,0,1,0,0,0,0,1,0,1,2,0,0,2,2,0,0,1,0,1,0,2,0,1,0,0,0,1,0,0},{2,0,0,0,2,2,0,2,0,0,2,2,1,0,0,2,0,2,1,0,0,0,0,2,2,0,2,2,0,0},{1,0,0,1,0,2,2,2,1,2,1,1,0,0,1,1,1,2,1,0,1,2,1,0,0,0,0,0,2,0},{2,0,1,2,2,2,1,0,1,2,1,1,0,1,0,0,0,2,0,2,2,0,2,0,1,2,0,2,0,1},{0,1,0,1,1,2,2,2,2,0,1,1,1,0,1,0,2,2,1,1,0,0,2,0,2,2,0,1,0,2},{1,1,1,2,1,2,0,0,1,0,0,0,2,0,0,2,0,0,0,0,1,1,2,2,2,2,1,1,2,0},{1,2,2,1,2,1,0,1,2,2,1,1,1,1,2,2,2,0,2,1,2,0,0,2,0,0,1,0,1,0},{1,2,1,0,0,0,1,0,1,0,1,1,0,1,0,0,0,0,0,0,2,1,2,2,0,0,2,0,1,2},{1,1,2,0,0,0,1,2,2,2,2,0,0,2,2,1,2,1,1,0,0,2,1,2,0,1,0,1,1,1},{2,2,0,2,1,1,2,1,2,0,0,2,1,1,1,0,0,1,1,0,0,0,0,2,2,2,2,1,1,0}};
//        int[][] grid = {{0,2,0,0,0,0,0},{0,0,0,2,2,1,0},{0,2,0,0,1,2,0},{0,0,2,2,2,0,2},{0,0,0,0,0,0,0}};
        int[][] grid = {{0,2,0,0,1},{0,2,0,2,2},{0,2,0,0,0},{0,0,2,2,0},{0,0,0,0,0}};//0
//        int[][] grid = {{0,0,0,0,0,0},{0,2,2,2,2,0},{0,0,0,1,2,0},{0,2,2,2,2,0},{0,0,0,0,0,0}};
//        int[][] grid = {{0,0,0,0,0},{0,2,0,2,0},{0,2,0,2,0},{0,2,1,2,0},{0,2,2,2,0},{0,0,0,0,0}};
//        int[][] grid = {{0,0,0,0},{0,1,2,0},{0,2,0,0}};
        m.maximumMinutes(grid);

    }

    public int maximumMinutes(int[][] grid) {
        int h = grid.length;
        int c = grid[0].length;
        System.out.println("---原始--------------------");
        for (int i=0;i<h;i++){
            for (int j=0;j<c;j++){
                System.out.print(grid[i][j] + "\t");
            }
            System.out.println();
        }
        int[][] run = new int[grid.length][grid[0].length];
        int[][] huo = new int[grid.length][grid[0].length];

        for (int i=0;i<h;i++){
            for (int j=0;j<c;j++){
                run[i][j] = Integer.MAX_VALUE;
                huo[i][j] = Integer.MAX_VALUE;
            }
        }
        run[0][0] = 0;

        db(grid,run,0,0,h-1,c-1);
        if(run[h-1][c-1]==Integer.MAX_VALUE){
            return -1;
        }
        System.out.println("---人--------------------");
        for (int i=0;i<h;i++){
            for (int j=0;j<c;j++){
                System.out.print(run[i][j] + "\t");
            }
            System.out.println();
        }

        System.out.println("-----------------------");

        for (int i=0;i<h;i++){
            for (int j=0;j<c;j++){
                if(grid[i][j]==1){
                    huo[i][j] = 0;
                    dbHuo(grid,huo,i,j,h-1,c-1);
                }
            }
        }
        System.out.println("-----火------------------");
        int min = Integer.MAX_VALUE;
        int mm = 0;
        boolean bb = false;
        int mmm = 0;
        for (int i=0;i<h;i++){
            for (int j=0;j<c;j++){
                System.out.print(huo[i][j] + "\t");
                if(run[i][j] != Integer.MAX_VALUE){
                    mm = huo[i][j]-run[i][j];
                    if(min > mm){
                        min = mm;
                        mmm =0;
                    }if(min == mm){
                        if(mmm!=0 &&i == h-1&&j == c-1){
                            bb = true;
                        }
                        mmm++;
                    }else if(min<mm){
                        mmm =0;
                    }
                }
            }
            System.out.println();
        }
        if(bb && run[h-1][c-2] != run[h-2][c-1]){
            min --;
        }
        if(min > 1000000000){
            min = 1000000000;
        }
        if(min<0){
            min = -1;
        }
        System.out.println(min);
        return min;
    }

    public boolean db(int[][] grid,int[][] run,int h,int c,int hh,int cc){//h c  当前位置
        if(h == hh && c == cc){
            return true;
        }
        boolean b = false;

        int k = run[h][c];
        if(h-1>=0 && grid[h-1][c] == 0){
            if((k+1)<run[h-1][c]){
                run[h-1][c] = k+1;
                if(db(grid,run,h-1,c,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h-1][c]){
                b=true;
            }
        }
        if(h+1<=hh && grid[h+1][c] == 0){
            if((k+1)<run[h+1][c]){
                run[h+1][c] = k+1;
                if(db(grid,run,h+1,c,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h+1][c]){
                b=true;
            }
        }
        if(c-1>=0 && grid[h][c-1] == 0){
            if((k+1)<run[h][c-1]){
                run[h][c-1] = (k+1);
                if(db(grid,run,h,c-1,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h][c-1]){
                b=true;
            }
        }
        if(c+1<=cc && grid[h][c+1] == 0){
            if((k+1)<run[h][c+1]){
                run[h][c+1] = k+1;
                if(db(grid,run,h,c+1,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h][c+1]){
                b=true;
            }
        }
        if(!b){
            run[h][c] = Integer.MAX_VALUE;
        }
        return b;
    }
    public boolean dbHuo(int[][] grid,int[][] run,int h,int c,int hh,int cc){//h c  当前位置
        if(h == hh && c == cc){
            return true;
        }
        boolean b = false;

        int k = run[h][c];
        if(h-1>=0 && grid[h-1][c] != 2){
            if((k+1)<run[h-1][c]){
                run[h-1][c] = k+1;
                if(dbHuo(grid,run,h-1,c,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h-1][c]){
                b=true;
            }
        }
        if(h+1<=hh && grid[h+1][c] != 2){
            if((k+1)<run[h+1][c]){
                run[h+1][c] = k+1;
                if(dbHuo(grid,run,h+1,c,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h+1][c]){
                b=true;
            }
        }
        if(c-1>=0 && grid[h][c-1] != 2){
            if((k+1)<run[h][c-1]){
                run[h][c-1] = (k+1);
                if(dbHuo(grid,run,h,c-1,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h][c-1]){
                b=true;
            }
        }
        if(c+1<=cc && grid[h][c+1] != 2){
            if((k+1)<run[h][c+1]){
                run[h][c+1] = k+1;
                if(dbHuo(grid,run,h,c+1,hh,cc)){
                    b=true;
                }
            }else if((k+1)==run[h][c+1]){
                b=true;
            }
        }
        if(!b){
            run[h][c] = Integer.MAX_VALUE;
        }
        return b;
    }

}

